package q338_countBits;

public class Solution_3 {
    /*
    动态规划：
    考虑一个问题 对于一个数字 x 如果能够找到一个最大的数y 使得 y <= x 并且y是2的指数
    那么显然 对于x的二进制表示 其最左侧第一个1也就是最大位置的1 与 y 是一致的
    并且考虑 z = x - y 显然有 dp[x] = dp[z] + 1 因为z只比x的最高位置少了一个1
    因此我们每次记录一个highBit也就是2的指数时 然后用动态规划即可计算0 - n的所有1的个数
     */
    public int[] countBits(int n) {
        int[] res = new int[n + 1];
        int highBit = 0;
        for (int i = 1; i <= n; i++) {
            if ((i & (i - 1)) == 0) highBit = i;
            res[i] = res[i - highBit] + 1;
        }

        return res;
    }
}
